﻿
using System;
using System.Drawing;
using System.Collections.Generic;

using GECS.Object;
using GECS.MapEngine;

namespace GECS.Collision {

	/// <summary>
	/// A QuadTree implementation to resolve collisions on the map.
	/// </summary>
	public class QuadTree : ICollisionEngine {

        private int MAX_OBJECTS = 10;
        private int level;

        private List<GObject> objects = null;
        private List<GObject> retriveList = null;

        private Rectangle bounds;

        private QuadTree[] nodes;

        /// <summary>
        /// Constructs a QuadTree to resolve collisions
        /// </summary>
        public QuadTree() : this(0, MapView.VisibleRect) {}

        /// <summary>
        /// Constructs a QuadTree at a level as a node
        /// </summary>
        /// <param name="l">Level ID</param>
        /// <param name="b">Area of this node</param>
        public QuadTree(int l, Rectangle b) {
            level = l;
            bounds = b;
            objects = new List<GObject>();
            retriveList = new List<GObject>();
            nodes = new QuadTree[4];
        }

        /// <summary>
		/// Sets the bounds of the visible area of the map.
		/// </summary>
		/// <param name="x">The x-coordinate of the top left point</param>
		/// <param name="y">The y-coordinate of the top left point</param>
		/// <param name="width">The width of the visible area</param>
		/// <param name="height">The height of the visible area</param>
        public void SetBounds(int x, int y, int width, int height) {
            bounds.X = x;
            bounds.Y = y;
            bounds.Width = width;
            bounds.Height = height;
            Clear();
            Split();
        }

		/// <summary>
		/// Clear the objects in the engine. (Doesn't clear the MAP)
		/// </summary>
        public void Clear() {
            objects.Clear();
            for (int i=0; i<nodes.Length; i++) {
                if (nodes[i] != null) {
                    nodes[i].Clear();
                    nodes[i] = null;
                }
            }
        }

		/// <summary>
		/// Splits the QuadTree into sub nodes.
		/// </summary>
        private void Split() {
            int subWidth = bounds.Width/2;
            int subHeight = bounds.Height/2;
            int x = bounds.X;
            int y = bounds.Y;
            nodes[0] = new QuadTree(level + 1, new Rectangle(x + subWidth, y, subWidth, subHeight));
            nodes[1] = new QuadTree(level + 1, new Rectangle(x, y, subWidth, subHeight));
            nodes[2] = new QuadTree(level + 1, new Rectangle(x, y + subHeight, subWidth, subHeight));
            nodes[3] = new QuadTree(level + 1, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight));
        }
		
        private int GetIndex(GObject r) {
            int index = -1;
            int verticalMidpoint = bounds.X + (bounds.Width / 2);
            int horizontalMidpoint = bounds.Y + (bounds.Height / 2);
            bool topQuadrant = (r.Y < horizontalMidpoint && r.Y + r.Height < horizontalMidpoint);
            bool bottomQuadrant = (r.Y > horizontalMidpoint);
            if (r.X < verticalMidpoint && r.X + r.Width < verticalMidpoint) {
                if (topQuadrant) {
                    index = 1;
                } else if (bottomQuadrant) {
                    index = 2;
                }
            } else if (r.X > verticalMidpoint) {
                if (topQuadrant) {
                    index = 0;
                } else if (bottomQuadrant) {
                    index = 3;
                }
            }
            return index;
        }

        private int GetIndex(Rectangle r) {
            int index = -1;
            int verticalMidpoint = bounds.X + (bounds.Width / 2);
            int horizontalMidpoint = bounds.Y + (bounds.Height / 2);
            bool topQuadrant = (r.Y < horizontalMidpoint && r.Y + r.Height < horizontalMidpoint);
            bool bottomQuadrant = (r.Y > horizontalMidpoint);
            if (r.X < verticalMidpoint && r.X + r.Width < verticalMidpoint) {
                if (topQuadrant) {
                    index = 1;
                } else if (bottomQuadrant) {
                    index = 2;
                }
            } else if (r.X > verticalMidpoint) {
                if (topQuadrant) {
                    index = 0;
                } else if (bottomQuadrant) {
                    index = 3;
                }
            }
            return index;
        }

		/// <summary>
		/// Inserts a GObject in to the engine.
		/// </summary>
		/// <param name="obj">The object to be added.</param>
        public void Insert(GObject obj) {
            if (nodes[0]!=null) {
                int index = GetIndex(obj);
                if (index!=-1) {
                    nodes[index].Insert(obj);
                    return;
                }
            }
            objects.Add(obj);
            if (objects.Count > MAX_OBJECTS) {
                if (nodes[0]==null) {
                    Split();
                }
                for (int i=0; i<objects.Count; i++) {
            		int index = GetIndex(objects[i]);
                    if (index!=-1) {
            			GObject o = objects[i];
                        nodes[index].Insert(o);
                        objects.RemoveAt(i);
                    }
                }
            }
        }
        
		/// <summary>
		/// Inserts a List of GObject's to the engine.
		/// </summary>
		/// <param name="objs">The list of objects.</param>
        public void Insert(List<GObject> objs){
        	foreach (GObject obj in objs){
        		Insert(obj);
        	}
        }
        
		/// <summary>
		/// Returns a list of objects that are likely collidable.
		/// </summary>
		/// <param name="r">The object to be tested.</param>
        public List<GObject> Retrieve(GObject r){
        	retriveList.Clear();
        	int index = GetIndex(r);
        	if (index != -1 && nodes[0] != null){
        		retriveList = nodes[index].Retrieve(r);
        	}
        	foreach (GObject obj in objects){
        		retriveList.Add(obj);
        	}
        	return retriveList;
        }
        
		/// <summary>
		/// Returns a list of objects that are likely to be present
		/// in a rectangle.
		/// </summary>
		/// <param name="r">The rectangle to be tested.</param>
        public List<GObject> Retrieve(Rectangle r){
        	retriveList.Clear();
        	int index = GetIndex(r);
        	if (index != -1 && nodes[0] != null){
        		retriveList = nodes[index].Retrieve(r);
        	}
        	foreach (GObject obj in objects){
        		retriveList.Add(obj);
        	}
        	return retriveList;
        }

    }

}
